package Tree_09.BinaryTree_01.DataStructure;

/*
 * @Author 罗
 * @date 2020/3/20 - 9:55 上午
 *
 */

import Tree_09.BinaryTree_01.Entity.HeroNode;


public class BinaryTree {

    private Node root;

    /**
     * 完成删除节点的操作
     * (1)如果删除的是叶子节点，则删除该节点
     * (2)如果删除的是非叶子节点，则删除该子树
     * <p>
     * 思路：
     * 首先去处理
     * 考虑如果树是空树root，如果如果只有一个root节点
     * 则等价将二叉树置null
     * 然后进行下面的步骤
     * 1.因为二叉树的父节点和子节点之间和单链表的相邻节点一样是单向的
     * 因此只能找到要删除节点的前一个节点，将其指向的要删除节点的指针(left,right)置null
     * 2.如果当前节点的左节点不为null，并且左节点就是要删除的节点
     * 就node.left = null
     * 并且就返回（结束递归删除）
     * 3.如果当前节点的右节点不为null，并且右节点就是要删除的节点
     * 就node.right = null
     * 并且就返回（结束递归删除）
     * 4.如果第二步、第三步没有删除节点，那么就要向左子树进行递归删除
     * 5.如果左子树递归删除也失败，就需要向右子树递归删除
     *
     * @param id
     */
    public HeroNode delete(int id) {
        if (root == null) {
            System.err.println("该数没有节点，删除失败");
            return null;
        }

        if (root.item.id == id) {
            root = null;
            return new HeroNode();
        }
        Node temp = root;


        return findBefore(temp, id).item;

    }

    public Node findBefore(Node temp, int id) {
        if (temp == null) {
            return null;
        }
        if (id < temp.item.id) {
            if (temp.left != null) {
                if (findBefore(temp.left, id).item.id == id) {

                    /*只删除本节点，*/
                    deleteFatherAndJointSonNode(temp, Side.left);
                    return temp;
                } else {
                    findBefore(temp.left, id);
                }
            }
        } else if (id > temp.item.id) {
            if (temp.right != null) {
                if (findBefore(temp.right, id).item.id == id) {
                    deleteFatherAndJointSonNode(temp, Side.right);
                    return temp;
                } else {
                    findBefore(temp.right, id);
                }
            }
        }
        return temp;
    }

    /**
     * @param father
     */
    private void deleteFatherAndJointSonNode(Node father, Side side) {
        /*
         *
         * 删除父节点右边的节点
         * 假设父节点右边的节点只有一个子节点
         * 并把父节点 指向 父节点右边的节点的其中一个有效节点
         *
         * 如果只有一个子节点
         * 1.只有右边节点有数据
         * */
        if (side == Side.right) {

            if (father.right.left == null && father.right.right != null) {
                /*
                 * 2.将父节点指向孙节点
                 * */
                father.right = father.right.right;
            } else if (father.right.left != null && father.right.right == null) {
                father.right = father.right.left;
            } else {
                deleteLeafNode(father, side);
            }

        } else {
            /*
             * 删除父节点左边的节点
             * 假设父节点左边的节点只有一个子节点
             * 并把父节点 指向 父节点左边的节点的其中一个有效节点
             *
             * 如果只有一个子节点
             * 1.只有右边节点有数据
             * */
            if (father.left.left == null && father.left.right != null) {
                /*
                 * 2.将父节点指向孙节点
                 * */
                father.left = father.left.right;
            } else if (father.left.left != null && father.left.right == null) {
                father.left = father.left.left;
            } else {
                deleteLeafNode(father, side);
            }
        }
    }


    private void deleteLeafNode(Node father, Side side) {
        if (side == Side.left) {
            if (father.left.left == null && father.left.right == null) {
                father.left = null;
            }
        } else {
            if (father.right.left == null && father.right.right == null) {
                father.right = null;
            }
        }
    }

    enum Side {
        left, right
    }

    /**
     * 后序查找
     *
     * @param id
     * @return
     */
    public HeroNode findBySuffix(int id) {
        Node temp = root;
        return findBySuffix(temp, id, 0);
    }

    public HeroNode findBySuffix(Node temp, int id, int count) {

        if (temp == null) {
            return null;
        }

        HeroNode result = null;
        if (temp.left != null) {
            result = findBySuffix(temp.left, id, count);
        }
        if (result != null) {
            return result;
        }
        if (temp.right != null) {
            result = findBySuffix(temp.right, id, count);
        }
        if (result != null) {
            return result;
        }

        System.out.println("第" + count + "次查找，当前节点是" + temp.item);
        count++;

        if (temp.item.id == id) {
            return temp.item;
        } else {
            return null;
        }
    }

    /**
     * 中序遍历查找
     *
     * @param id
     * @return
     */
    public HeroNode findByInfix(int id) {
        Node temp = root;
        return findByInfix(temp, id, 0);
    }

    public HeroNode findByInfix(Node temp, int id, int count) {


        if (temp == null) {
            return null;
        }


        HeroNode result = null;

        if (temp.left != null) {
            result = findByInfix(temp.left, id, count);
        }
        if (result != null) {
            return result;
        }
        /*
         * 写在判断条件之前才是真实的
         * */
        System.out.println("第" + count + "次查找，当前节点是" + temp.item);
        count++;
        if (temp.item.id == id) {
            return temp.item;
        }

        if (temp.right != null) {
            result = findByInfix(temp.right, id, count);
        }
        return result;
    }


    public HeroNode findByPrefix(int id) {
        Node temp = root;
        return findByPrefix(temp, id, 0);
    }

    /**
     * 前序遍历查找
     *
     * @param temp
     * @param id
     * @param count
     * @return
     */
    public HeroNode findByPrefix(Node temp, int id, int count) {


        if (temp == null) {
            return null;
        }


        System.out.println("第" + count + "次查找，当前节点是" + temp.item);
        count++;
        /*
         * 比较当前节点是不是要查找的节点
         * */
        if (temp.item.id == id) {
            return temp.item;
        }
        /*
         * 用于判断是否找到
         * */
        HeroNode result = null;
        if (temp.left != null) {
            /*
             * 不为空，继续递归前序查找
             * */
            result = findByPrefix(temp.left, id, count);
        }
        /*
         * 如果结果找到，则直接返回
         * */
        if (result != null) {
            return result;
        }
        /*
         * 之前的递归左查找没有找到
         *       继续右查找
         * */

        if (temp.right != null) {
            result = findByPrefix(temp.right, id, count);
        }
        return result;
    }


    /**
     * 后序遍历
     * 父节点最后输出
     * 输出顺序：左节点->右节点->父节点
     */
    public void suffixList() {
        Node temp = root;
        suffix(temp, 0);
    }

    protected void suffix(Node temp, int count) {
        if (temp == null) {
            return;
        }
        count++;
        if (temp.left != null) {
            suffix(temp.left, count);
        }
        if (temp.right != null) {
            suffix(temp.right, count);
        }
        for (int i = 0; i < count; i++) {
            System.out.print("--");
        }
        System.out.println(temp.item);
    }

    /**
     * 中序遍历
     * 父节点第二个输出
     * 输出顺序：左节点->父节点->右节点
     */
    public void infixList() {
        Node temp = root;
        infix(root, 0);
    }

    protected void infix(Node temp, int count) {
        if (temp == null) {
            return;
        }

        count++;


        if (temp.left != null) {
            /*
             * 递归向左子树中序遍历
             * */
            infix(temp.left, count);


        }
        /*
         * 输出父节点
         * */

        for (int i = 0; i < count; i++) {
            System.out.print("--");
        }
        System.out.println(temp.item);

        if (temp.right != null) {
            /*
             * 向右子树中序遍历
             * */
            infix(temp.right, count);

        }
    }


    /**
     * 前序遍历
     * 父节点第一个输出
     * 输出顺序：父节点->左节点->右节点
     */
    public void prefixList() {
        Node temp = root;
        preOrder(temp, 0);
    }

    protected void preOrder(Node node, int count) {
        if (node == null) {
            return;
        }
        for (int i = 0; i < count; i++) {
            System.out.print("--");
        }
        count++;
        /*
         * 先输出父节点
         * */
        System.out.println(node.item);
        if (node.left != null) {
            /*
             * 递归向左子树前序遍历
             * */
            preOrder(node.left, count);
        }
        if (node.right != null) {
            /*
             * 递归向右子树前序遍历
             * */
            preOrder(node.right, count);
        }
    }

    public HeroNode findById(int id) {
        Node temp = root;
        while (true) {
            if (id > temp.item.id) {
                if (temp.right != null) {
                    temp = temp.right;
                } else {
                    System.err.println("未找到该节点");
                    return null;
                }
            } else if (id < temp.item.id) {
                if (temp.left != null) {
                    temp = temp.left;
                } else {
                    System.err.println("未找到该节点");
                    return null;
                }
            } else {
                return temp.item;
            }
        }
    }

    public void addOrderly(HeroNode heroNode) {
        if (root == null) {
            root = new Node(heroNode);
            return;
        }
        Node temp = root;
        while (true) {
            if (heroNode.id > temp.item.id) {

                if (temp.right != null) {
                    temp = temp.right;
                } else {
                    temp.right = new Node(heroNode);
                    return;
                }
            } else if (heroNode.id < temp.item.id) {

                if (temp.left != null) {
                    temp = temp.left;
                } else {
                    temp.left = new Node(heroNode);
                    return;
                }
            } else {
                System.err.println("节点ID已经存在");
                return;
            }

        }
    }

    public BinaryTree() {

    }
}
